The mutual exclusion problem is concerned with ensuring that two concurrently executing threads (also known as processes) of control do not both reach a critical section of code at the same time. The critical section of code is that section of code in which a shared resource is accessed. Mutual exclusion is important if a program requires exclusive control over resources in order to be sure of giving the right result. A key bottleneck that limits performance is the implementation of “locking”, which is a mechanism that ensures mutual exclusion.
Typically, a hardware “lock” instruction (such as XCHNG), or variant thereof, is used to manage exclusive access. A lock instruction ensures an atomic read-modify-write transaction, thus guaranteeing that only one thread can acquire lock ownership at a time. One disadvantage of a lock instruction is that it has a performance penalty on modern high performance microprocessors.
In Java, a Java Virtual Machine (JVM) manages this by avoiding the use of a lock instruction as much as possible. A JVM is a machine in software that provides the run-time environment for Java programs, and is responsible for implementing the required locking mechanism. Depending on the implementation approach taken by the JVM, there can be a wide variation in performance on e-business (electronic business) software running on a server.
Alternatively, a Java programmer may use the “synchronized” keyword to ensure mutual exclusion. FIG. 1 shows the typical usage of this keyword in a Java program. In this example, a procedure called “manipulate” (line 1) comprises code (lines 2 and 6), and utilizes the “synchronized” keyword (line 3) to obtain a lock on the object “syncObj” prior to running a section of the code which uses the object “syncObj” (line 4). Use of this primary mechanism for ensuring mutual exclusion of a shared resource has its disadvantages. When multiple threads contend for a shared resource, the performance of a computer system can be drastically impacted.
Consequently, Java programmers may use other existing algorithms to ensure mutually exclusive access to a shared resource. One such algorithm is a classic one of G. L. Peterson, as illustrated in pseudocode in FIG. 2. Peterson's algorithm provides one way of achieving mutual exclusion for N concurrent threads. The basic premise of the Peterson algorithm is that for a given thread i, its critical section (line 13) may only be entered if one of the while-loop (lines 9-11) conditions tests false. The first condition (line 9) is false if thread i is the only thread running (j!=i, where j is a thread, other than i, currently executing); the second condition (line 10) becomes false if thread j has completed, where thread j resets the flag variable to −1 upon completion; and the last condition (line 11) becomes false if another thread enters the processing queue.
One disadvantage of the Peterson algorithm is poor performance as the number of threads increases. A thread that owns a lock can lose the CPU (central processing unit) in the normal course of operating system thread scheduling. Thereafter, every other thread in the run queue gets the CPU, spins for its quantum, and then loses the CPU to the next thread in the queue. The more threads there are, the less quantum of time a given thread has. Moreover, the variables are shared variables in memory, further causing processing delays. The more threads, the worse this problem becomes. As a result, not much useful work is accomplished.